A primary goal in digital communications is the transmission of data in error-free form. During transmission, the data is subjected to noise which may cause errors in the received data. To improve the reliability of data transmission, one of a variety of possible error correction techniques is commonly used. For example, a known error correction technique is convolutional coding. This technique provides an effective error correction capability but requires sophisticated decoding techniques. An optional solution for decoding convolutional codes is credited to Andrew Viterbi and is well known as the Viterbi algorithm.
The Viterbi algorithm is a recursive solution to the problem of estimating the state sequence of a discrete-time finite-state Markov process observed in memory-less noise. Viterbi decoding is not restricted to convolutional codes, but can be applied to other sequence estimation problems such as channel equalizers. Decoding of convolutional codes requires making probability decisions based on a sequence of received bits rather than on an individual bit-by-bit basis. The basic operation of the Viterbi decoder is to select the path through a trellis, in the presence of noise, that represents the most likely sequence that was generated by a convolutional encoder.
The Viterbi algorithm makes use of the recurrent properties of convolutional codes to provide an efficient solution to this problem. At each symbol period the algorithm generates a metric, a measure of probability, for each branch. The best path of each state is then determined by examining the accumulated metrics from all paths entering the state and selecting the one with the best metric. The other paths are discarded. Therefore, paths with errors will accumulate lower metrics and therefore be discarded leaving only the path that represents the sequence which was most likely generated by the encoder.
To implement the Viterbi algorithm, a plurality of add/compare/select (ACS) operations must be performed to calculate the best path to each state. In today's central processing unit (CPU) architectures which implement the Viterbi algorithm, sequential processing is utilized to perform the ACS operations. In a CPU approach, a plurality of sequential memory fetches, addition, storage and comparison operations must be executed. The sequential operation limits data throughput due to the high number of instructions needed per symbol or data bit.
Each path or branch has a unique value or metric which is represented by a positive or negative multi-bit binary value. Each path metric P and branch metric B is defined as a measure of distance determined by some form of comparison between a received symbol and a corresponding path or branch in a trellis. As used herein, the term pair "old" and "new" are convenient abbreviations to distinguish successive time points j-1, j, j+1, such as, for example, "old"="j-1" and "new"="j" or, for example, "old"="j" and new="j+1". Indices i and j can be combined with integer numbers by addition ("+"), subtraction ("-"), multiplication ("*"), and division ("/"). For convenience, the multiplication symbol "*" can be left out. For example, 2i with i=2 equals 2*2=4. Relations of the type "a&gt;b" and "a&lt;b" have the logical values true (e.g., for 3&gt;2) or false (e.g., for 3&lt;2). The calculation operation for path metrics P and branch metrics B is not relevant to the present invention and will not be further discussed since metric calculation is well documented in existing literature.
FIG. 1 illustrates a prior art example of a trellis diagram for an N=16 state code. Blocks 41, 42, and 43 indicate first, second and third pluralities of path metrics {P (n, j-1) }, {P (n, j)} and {P (n, j+1)} (n=0 to N-1=15) for successive time points j-1, j, and j+1, respectively. Pluralities are illustrated by { }. Indices n are intended to be cyclical, for example, 8+8=16 is considered as 0; 8+9=1 and so on. For simplicity, indices j-1, j, and j+1 are not shown inside the blocks. N is the number of possible states for a convolutional code with K coefficients and is generally N=2.sup.K-1. Index n is also given as 2i, 2i+1, 2i+2 and so on for P (n, j-1) (block 41), as i, i+1 and so on for P (n, j) (block 42), and as i/2, i/2+1 and so on for P (n, j) (block 43). Even index i goes from 0 to N-2. Lines between blocks 41, 42 and 43 indicate the transitions of path metrics P (j-1) to P (j) and to P (j+1). In a representative example, butterfly 44 (bold lines) between block 41 and 42, symbolizes the transition of old path metrics P (j-1) to new path metrics P (j). For convenience of explanation for i=2, encircled reference numbers 91-95 point to P (2i, j-1)=P (4, j-11), P (2i+1, j-1)=P (5, j-1) of block 41, to P (i, j)=P (2, j), P (i+N/2, j)=P (10, j) of block 42, and to a branch metric B (i, j), respectively. N/2 butterflies (e.g., 8) are needed to transform {P (n, j-1)} to {P (n, j)}. As an example, and not intended to be limiting, the calculation for butterfly 44 will be explained in detail in connection with FIG. 2.
FIG. 2 illustrates a simplified flow diagram of a prior art calculation method for implementing the Viterbi algorithm. Old metrics P (2i, j-1) on line 91 and P (2i+1, j-1) on line 92 (cf. encircled numbers in FIG. 1) are combined with +B (i, j) at line 95 to obtain new path metrics P (i, j) at line 93 and P (i+N/2, j) at line 94. Block 11 illustrates that + B (i, j) is inverted to - B (i, j). As mentioned above, the Viterbi algorithm comprises the steps of adding (A) (blocks 12, 14, 16, and 18), comparing (C) (blocks 22 and 24), and selecting (S) (blocks 32 and 34).
(A) In the step of adding, block 12 provides P (2i, j-1)+B (i, j) at line 13, block 14 provides P (2i+1, j-1)-B (i, j) at line 15, block 16 provides P (2i, j-1)-B (i, j) at line 17, and block 18 provides P (2i+1, j-1)+B (i, j) at line 19. This resulting sums P+B are communicated to comparators 22 and 24. PA1 (C) In the step of comparing, block 22 makes a decision D (i, j). D (i, j) becomes D (i, j)=0 for a true relation: EQU P(2i, j-1)+B(i, j)&gt;P (2i+1,j-1)-B(i, j). (1) PA1 Otherwise, D (i, j) becomes D (i, j)=1 for a true relation: EQU P (2i, j-1)+B(i, j)&lt;P(2i+1, j-1)-B(i, j). (2) PA1 Relations (2) and (3) differ only by the "&gt;,&lt;"-symbols, so that the logical values true and false are inverted. Block 24 makes decision D (i+N/2, j) which becomes D (i+N/2, j)=0 for a true relation EQU P(2i, j-1)-B(i, j)&gt;P(2i+1, j-1)+B(i,j) (3) PA1 The decision is D (i+N/2, j)=1 for a true relation EQU P(2i, j-1)-B(i, j)&lt;P(2i+1, j-1)+B(i,j) (4) PA1 Relations (4) and (5) differ also only by the "&gt;,&lt;"-symbols. Decisions D (i, j) and D (i+N/2, j) are communicated to blocks 32 and 34 via control lines 36 and 38, respectively. PA1 (S) In the step of selecting, block 32 provides new EQU P(i, j)=P(2i, j-1)+B(i, j) for D(i, j)=0 (5) PA1 (left side of (2) and (3)) or provides new EQU P(i, j)=P(2i+1, j-1)-B(i, j) for D(i, j)=1 (6) PA1 (right side of (2) and (3)). Block 34 provides new EQU P(i+N/2, j)=P(2i, j-1)-B(i, j) for D(i+N/2, j)=0 (7) PA1 (left side of (4) and (5)) and provides new EQU P(i+N/2, j)=P(2i+1, j31 1)+B (i, j) for D(i+N/2, j)=1 (8) PA1 (right side of (4) and (5)).
It is inconvenient to have for one butterfly 44 a number of 4 add calculations (blocks 12, 14, 16, 18) in step (A) and 2 calculations (blocks 22, 24) in step (C). To transform a first plurality {P (j-1)} to a second plurality {P (j)} by 8 butterflies, 8*(4+2)=48 calculations are required.
In a communication system, Viterbi butterflies are, preferably, calculated by a digital signal processors. Such processors are usually part of communication system but have limited time resources. The calculation time increases linearly with the number of butterflies and should be reduced.
Accordingly, it is an object of the present invention to provide an improved method and ACS circuit for implementing the Viterbi decoding function in a digital communications system.